{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Indices With Index and Value Difference II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findIndices"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找出满足差值条件的下标 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始、长度为 <code>n</code> 的整数数组 <code>nums</code> ，以及整数 <code>indexDifference</code> 和整数 <code>valueDifference</code> 。</p>\n",
    "\n",
    "<p>你的任务是从范围 <code>[0, n - 1]</code> 内找出&nbsp; <strong>2</strong> 个满足下述所有条件的下标 <code>i</code> 和 <code>j</code> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>abs(i - j) &gt;= indexDifference</code> 且</li>\n",
    "\t<li><code>abs(nums[i] - nums[j]) &gt;= valueDifference</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>返回整数数组 <code>answer</code>。如果存在满足题目要求的两个下标，则 <code>answer = [i, j]</code> ；否则，<code>answer = [-1, -1]</code> 。如果存在多组可供选择的下标对，只需要返回其中任意一组即可。</p>\n",
    "\n",
    "<p><strong>注意：</strong><code>i</code> 和 <code>j</code> 可能 <strong>相等</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [5,1,4,1], indexDifference = 2, valueDifference = 4\n",
    "<strong>输出：</strong>[0,3]\n",
    "<strong>解释：</strong>在示例中，可以选择 i = 0 和 j = 3 。\n",
    "abs(0 - 3) &gt;= 2 且 abs(nums[0] - nums[3]) &gt;= 4 。\n",
    "因此，[0,3] 是一个符合题目要求的答案。\n",
    "[3,0] 也是符合题目要求的答案。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,1], indexDifference = 0, valueDifference = 0\n",
    "<strong>输出：</strong>[0,0]\n",
    "<strong>解释：</strong>\n",
    "在示例中，可以选择 i = 0 和 j = 0 。 \n",
    "abs(0 - 0) &gt;= 0 且 abs(nums[0] - nums[0]) &gt;= 0 。 \n",
    "因此，[0,0] 是一个符合题目要求的答案。 \n",
    "[0,1]、[1,0] 和 [1,1] 也是符合题目要求的答案。 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3], indexDifference = 2, valueDifference = 4\n",
    "<strong>输出：</strong>[-1,-1]\n",
    "<strong>解释：</strong>在示例中，可以证明无法找出 2 个满足所有条件的下标。\n",
    "因此，返回 [-1,-1] 。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n == nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>0 &lt;= indexDifference &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= valueDifference &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-indices-with-index-and-value-difference-ii](https://leetcode.cn/problems/find-indices-with-index-and-value-difference-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-indices-with-index-and-value-difference-ii](https://leetcode.cn/problems/find-indices-with-index-and-value-difference-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,1,4,1]\\n2\\n4', '[2,1]\\n0\\n0', '[1,2,3]\\n2\\n4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:\n",
    "        ans = [-1, -1]\n",
    "        l = len(nums)\n",
    "        for i in range(l-indexDifference):\n",
    "            for j in range(i+indexDifference, l):\n",
    "                if abs(nums[i]-nums[j]) >= valueDifference:\n",
    "                    ans = [i, j]\n",
    "                    return ans\n",
    "        return ans\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:\n",
    "        def func(nums,indexDifference,valueDifference):\n",
    "            n = len(nums)\n",
    "\n",
    "            for i in range(indexDifference,n):\n",
    "                for j in range(i-indexDifference+1):\n",
    "                    if abs(nums[i]-nums[j])>=valueDifference:\n",
    "                        return [i,j]\n",
    "\n",
    "            return [-1,-1]\n",
    "        \n",
    "        return func(nums,indexDifference,valueDifference)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:\n",
    "        ans=[-1,-1]\n",
    "        for i in range(len(nums)-indexDifference):\n",
    "            for j in range(i+indexDifference,len(nums)):\n",
    "                if abs(nums[i]-nums[j])>=valueDifference:\n",
    "                    ans[0]=i\n",
    "                    ans[1]=j\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        for i in range(n-indexDifference):\n",
    "            for j in range(i+indexDifference, n):\n",
    "                if abs(nums[i] - nums[j]) >= valueDifference:\n",
    "                    return [i, j]\n",
    "\n",
    "        return [-1, -1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ma = max(nums)\n",
    "        mi = min(nums)\n",
    "        for i in range(n):\n",
    "            if (nums[i]-mi < valueDifference) and (ma-nums[i] < valueDifference):\n",
    "                continue\n",
    "            for j in range(i+indexDifference, n):\n",
    "                if abs(nums[i]-nums[j]) >= valueDifference:\n",
    "                    return [i,j]\n",
    "        return [-1,-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:\n",
    "        if len(nums) <= indexDifference:\n",
    "            return [-1, -1]\n",
    "\n",
    "        mx = -float(\"inf\")\n",
    "        mn = float(\"inf\")\n",
    "        for j in range(indexDifference, len(nums)):\n",
    "            i = j-indexDifference\n",
    "            if nums[i] > mx:\n",
    "                mx_id = i\n",
    "                mx = nums[i]\n",
    "            if nums[i] < mn:\n",
    "                mn_id = i\n",
    "                mn = nums[i]\n",
    "            \n",
    "            if abs(mx-nums[j]) >= valueDifference:\n",
    "                return [mx_id, j]\n",
    "            if abs(mn-nums[j]) >= valueDifference:\n",
    "                return [mn_id, j]\n",
    "        return [-1, -1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:\n",
    "\n",
    "        max_idx = min_idx = 0\n",
    "\n",
    "        for j in range(indexDifference, len(nums)):\n",
    "\n",
    "            i = j - indexDifference\n",
    "\n",
    "            if nums[i] > nums[max_idx]:\n",
    "\n",
    "                max_idx = i\n",
    "\n",
    "            elif nums[i] < nums[min_idx]:\n",
    "\n",
    "                min_idx = i\n",
    "\n",
    "            if nums[max_idx] - nums[j] >= valueDifference:\n",
    "\n",
    "                return [max_idx, j]\n",
    "\n",
    "            if nums[j] - nums[min_idx] >= valueDifference:\n",
    "\n",
    "                return [min_idx, j]\n",
    "\n",
    "        return [-1, -1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:\n",
    "        # List1 = []\n",
    "        # lenList = len(nums)\n",
    "        # for i in range(lenList):\n",
    "        #     for j in range(i+indexDifference,lenList):\n",
    "        #         if(abs(nums[i]-nums[j]) >= valueDifference):\n",
    "        #             List1 = [i,j]\n",
    "        #             break\n",
    "        #     if(len(List1)==0):\n",
    "        #         List1 = [-1,-1]\n",
    "\n",
    "        # max_idx = min_idx = 0\n",
    "        # for j in range(indexDifference, len(nums)):\n",
    "        #     i = j - indexDifference\n",
    "        #     if nums[i] > nums[max_idx]:\n",
    "        #         max_idx = i\n",
    "        #     elif nums[i] < nums[min_idx]:\n",
    "        #         min_idx = i\n",
    "        #     if nums[max_idx] - nums[j] >= valueDifference:\n",
    "        #         return [max_idx, j]\n",
    "        #     if nums[j] - nums[min_idx] >= valueDifference:\n",
    "        #         return [min_idx, j]\n",
    "        # return [-1, -1]\n",
    "\n",
    "          #记录左边合法的最大值和最小值\n",
    "        n=len(nums)\n",
    "        big=[i for i in range(n)]\n",
    "        small=[i for i in range(n)]\n",
    "        preSmall,preBig=0,0\n",
    "        for i in range(n):\n",
    "            if nums[i]<nums[preSmall]:\n",
    "                preSmall=i\n",
    "            if nums[i]>nums[preBig]:\n",
    "                preBig=i\n",
    "            big[i]=preBig\n",
    "            small[i]=preSmall\n",
    "        for i in range(n):\n",
    "            if i-indexDifference>=0:\n",
    "                j=big[i-indexDifference]\n",
    "                if abs(nums[i]-nums[j])>=valueDifference:\n",
    "                    return [i,j]\n",
    "                j=small[i-indexDifference]\n",
    "                if abs(nums[i]-nums[j])>=valueDifference:\n",
    "                    return [i,j]\n",
    "        return [-1,-1]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:\n",
    "        pre_min, pre_max, suf_min, suf_max = [nums[0]], [nums[0]], [nums[-1]], [nums[-1]]\n",
    "        lenth = len(nums)\n",
    "        for i in range(1, lenth):\n",
    "            pre_min.append(min(pre_min[-1], nums[i]))\n",
    "            pre_max.append(max(pre_max[-1], nums[i]))\n",
    "            \n",
    "        for i in range(lenth - 2, -1, -1):\n",
    "            suf_min.append(min(suf_min[-1], nums[i]))\n",
    "            suf_max.append(max(suf_max[-1], nums[i]))\n",
    "        \n",
    "        suf_min = suf_min[::-1]\n",
    "        suf_max = suf_max[::-1]\n",
    "        \n",
    "        \n",
    "        for i in range(lenth - indexDifference):\n",
    "            j = i + indexDifference\n",
    "            ans = []\n",
    "            sub = abs(pre_min[i] - suf_max[j])\n",
    "            print(sub, i, j)\n",
    "            \n",
    "            if sub >= valueDifference:\n",
    "                for idx in range(i + 1):\n",
    "                    if nums[idx] == pre_min[i]:\n",
    "                        ans.append(idx)\n",
    "                        break\n",
    "                for idx in range(j, lenth):\n",
    "                    if nums[idx] == suf_max[j]:\n",
    "                        ans.append(idx)\n",
    "                        break\n",
    "                return ans\n",
    "                \n",
    "                \n",
    "            sub = abs(pre_max[i] - suf_min[j])\n",
    "            if sub >= valueDifference:\n",
    "                for idx in range(i + 1):\n",
    "                    if nums[idx] == pre_max[i]:\n",
    "                        ans.append(idx)\n",
    "                        break\n",
    "                for idx in range(j, lenth):\n",
    "                    if nums[idx] == suf_min[j]:\n",
    "                        ans.append(idx)\n",
    "                        break\n",
    "                return ans\n",
    "        \n",
    "            \n",
    "        return [-1, -1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:\n",
    "        #记录左边合法的最大值和最小值\n",
    "        n=len(nums)\n",
    "        big=[i for i in range(n)]\n",
    "        small=[i for i in range(n)]\n",
    "        preSmall,preBig=0,0\n",
    "        for i in range(n):\n",
    "            if nums[i]<nums[preSmall]:\n",
    "                preSmall=i\n",
    "            if nums[i]>nums[preBig]:\n",
    "                preBig=i\n",
    "            big[i]=preBig\n",
    "            small[i]=preSmall\n",
    "        for i in range(indexDifference,n):\n",
    "                j=big[i-indexDifference]\n",
    "                if abs(nums[i]-nums[j])>=valueDifference:\n",
    "                    return [i,j]\n",
    "                j=small[i-indexDifference]\n",
    "                if abs(nums[i]-nums[j])>=valueDifference:\n",
    "                    return [i,j]\n",
    "        return [-1,-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIndices(self, nums: List[int], index: int, value: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        mi, mx = list(range(n)), list(range(n))\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if nums[i] <= nums[mx[i + 1]]:\n",
    "                mx[i] = mx[i + 1]\n",
    "            if nums[i] >= nums[mi[i + 1]]:\n",
    "                mi[i] = mi[i + 1]\n",
    "        # print(mi, mx)\n",
    "        for i in range(n):\n",
    "            if i + index < n:\n",
    "                if abs(nums[i] - nums[mx[i + index]]) >= value:\n",
    "                    return [i, mx[i + index]]\n",
    "                if abs(nums[i] - nums[mi[i + index]]) >= value:\n",
    "                    return [i, mi[i + index]]\n",
    "        return [-1, -1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        q_min = nums[indexDifference:] #最小堆\n",
    "        #最大堆\n",
    "        q_max = [-val for val in q_min]\n",
    "        heapq.heapify(q_min)\n",
    "        heapq.heapify(q_max)\n",
    "        # print(q_min)\n",
    "        # print(q_max)\n",
    "        #延迟删除 \n",
    "        if indexDifference == 0 and valueDifference == 0:\n",
    "            return [0, 0]\n",
    "        need_deleted = set()\n",
    "        for idx in range(n-indexDifference):\n",
    "        \n",
    "            #最小值\n",
    "            while q_min and q_min[0] in need_deleted:\n",
    "                need_deleted.remove(q_min[0])\n",
    "                heapq.heappop(q_min)\n",
    "            while q_max and -q_max[0] in need_deleted:\n",
    "                need_deleted.remove(-q_max[0] )\n",
    "                heapq.heappop(q_max)\n",
    "            min_val = q_min[0] if q_min else nums[idx]\n",
    "            max_val = q_max[0] if q_max else nums[idx]\n",
    "            if abs(min_val-nums[idx]) >= valueDifference:\n",
    "                for j in range(n-1, idx, -1):\n",
    "                    if nums[j] == min_val:\n",
    "                        return [idx,j ]\n",
    "            if abs(max_val+nums[idx]) >= valueDifference:\n",
    "                for j in range(n-1, idx, -1):\n",
    "                    if nums[j] == -max_val:\n",
    "                        return [idx, j]\n",
    "            need_deleted.add(nums[idx+indexDifference])\n",
    "        return [-1, -1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            if indexDifference > 0:\n",
    "                return [-1, -1]\n",
    "            \n",
    "            if  valueDifference == 0:\n",
    "                return [0, 0]\n",
    "            \n",
    "            return [-1, -1]\n",
    "\n",
    "        pre = [(nums[0], nums[0], 0, 0)] * n\n",
    "\n",
    "        for i in range(1, n):\n",
    "            v = nums[i]\n",
    "            (mi, ma, mii, mai) = pre[i-1]\n",
    "            if v < mi:\n",
    "                mi = v\n",
    "                mii = i\n",
    "            if v > ma:\n",
    "                ma = v\n",
    "                mai = i\n",
    "            pre[i] = (mi, ma, mii, mai)\n",
    "\n",
    "            if i >= indexDifference:\n",
    "                (mi, ma, mii, mai) = pre[i - indexDifference]\n",
    "                if abs(mi - v) >= valueDifference:\n",
    "                    return [mii, i]\n",
    "                \n",
    "                if abs(ma - v) >= valueDifference:\n",
    "                    return [mai, i]\n",
    "\n",
    "        return [-1, -1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:\n",
    "        s1 = deque()  # 最大值，单调减的栈\n",
    "        for i, x in enumerate(nums[indexDifference:], indexDifference):\n",
    "            while s1 and s1[-1][1] <= x:\n",
    "                s1.pop()\n",
    "            s1.append([i, x])\n",
    "        s2 = deque()  # 最小值，单调增的栈\n",
    "        for i, x in enumerate(nums[indexDifference:], indexDifference):\n",
    "            while s2 and s2[-1][1] >= x:\n",
    "                s2.pop()\n",
    "            s2.append([i, x])\n",
    "        # print(s1)\n",
    "        # print(s2)\n",
    "        for i, x in enumerate(nums):\n",
    "            while s1 and s1[0][0] - i < indexDifference:\n",
    "                s1.popleft()\n",
    "            while s2 and s2[0][0] - i < indexDifference:\n",
    "                s2.popleft()\n",
    "            if s1 and s1[0][1] - x >= valueDifference:\n",
    "                return [i, s1[0][0]]\n",
    "            if s2 and x - s2[0][1] >= valueDifference:\n",
    "                return [i, s2[0][0]]\n",
    "            if not s1 and not s2:\n",
    "                return [-1, -1]\n",
    "        return [-1, -1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:\n",
    "        N = len(nums)\n",
    "        data = [(nums[i], i) for i in range(N)]\n",
    "        data.sort()\n",
    "        nums.sort()\n",
    "        \n",
    "        maxs = [-inf]\n",
    "        mins = [inf]\n",
    "        for x, i in data:\n",
    "            maxs.append(max(maxs[-1], i))\n",
    "            mins.append(min(mins[-1], i))\n",
    "        \n",
    "        '''\n",
    "        1 2 3 5\n",
    "        \n",
    "        '''\n",
    "        for j in range(N):\n",
    "            x, i = data[j]\n",
    "            k = bisect_right(nums, x-valueDifference, hi=j+1)\n",
    "            if k >= N or nums[k] != x-valueDifference:\n",
    "                k -= 1\n",
    "            if i - mins[k+1] >= indexDifference:\n",
    "                return [mins[k+1], i]\n",
    "            if maxs[k+1] - i >= indexDifference:\n",
    "                return [maxs[k+1], i]\n",
    "        \n",
    "        return [-1,-1]\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        arr = [[0,0,0,0] for _ in range(n+1)]\n",
    "        arr[n] = [2**31, -1, 0, 0]\n",
    "        for j in range(n-1, -1, -1):\n",
    "            arr[j] = copy.copy(arr[j+1])\n",
    "            if arr[j+1][0] > nums[j]: \n",
    "                arr[j][0] = nums[j]\n",
    "                arr[j][2] = j\n",
    "            if arr[j+1][1] < nums[j]:\n",
    "                arr[j][1] = nums[j]\n",
    "                arr[j][3] = j\n",
    "        # print(arr)\n",
    "        for i in range(n-indexDifference):\n",
    "            if abs(nums[i]-arr[i+indexDifference][0]) >= valueDifference:\n",
    "                return [i, arr[i+indexDifference][2]]\n",
    "            if abs(nums[i]-arr[i+indexDifference][1]) >= valueDifference:\n",
    "                return [i, arr[i+indexDifference][3]]\n",
    "        return [-1, -1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:\n",
    "        sorted_nums = sorted(enumerate(nums), key=lambda x: x[1])\n",
    "        tmp=[0]*len(nums)\n",
    "        # print(sorted_nums)\n",
    "        bigtmp=[0]*len(nums)\n",
    "        smalltmp=[0]*len(nums)\n",
    "        bigindex=-1\n",
    "        smallindex=len(nums)+1\n",
    "        for i in range(len(nums)-1,-1,-1):\n",
    "            tmp[i]=sorted_nums[i][1]\n",
    "            if sorted_nums[i][0]>bigindex:\n",
    "                bigindex=sorted_nums[i][0]\n",
    "                bigtmp[i]=bigindex\n",
    "            else:\n",
    "                bigtmp[i]=bigindex\n",
    "            if sorted_nums[i][0]<smallindex:\n",
    "                smallindex=sorted_nums[i][0]\n",
    "                smalltmp[i]=smallindex\n",
    "            else:\n",
    "                smalltmp[i]=smallindex\n",
    "        # print(tmp)\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            position=bisect.bisect_left(tmp,tmp[i]+valueDifference)\n",
    "            if position<len(nums) and ( abs(sorted_nums[i][0]-smalltmp[position])>=indexDifference or abs(bigtmp[position]-sorted_nums[i][0])>=indexDifference):\n",
    "                for k in range(position,len(nums)):\n",
    "                    if abs(sorted_nums[i][0]-sorted_nums[k][0])>=indexDifference:\n",
    "                        return [sorted_nums[k][0],sorted_nums[i][0]]\n",
    "        return [-1,-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def findIndices(self, a: List[int], idx: int, val: int) -> List[int]:\n",
    "        n = len(a)\n",
    "        sl = SortedList()\n",
    "        m = 0\n",
    "        for i in range(n):\n",
    "            if i >= idx:\n",
    "                sl.add((a[i - idx], i - idx))\n",
    "                m += 1\n",
    "            k = sl.bisect_left((a[i] - val, n))\n",
    "            if k > 0:\n",
    "                return [i, sl[k - 1][1]]\n",
    "            k = sl.bisect_left((a[i] + val, 0))\n",
    "            if k < m:\n",
    "                return [i, sl[k][1]]\n",
    "            \n",
    "        return [-1, -1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:\n",
    "        L = SortedList()\n",
    "        front,tail = 0,indexDifference\n",
    "        while tail<len(nums):\n",
    "            L.add((nums[front], front))\n",
    "            if abs(L[0][0]-nums[tail])>=valueDifference:\n",
    "                return [L[0][1],tail]\n",
    "            if abs(L[-1][0]-nums[tail])>=valueDifference:\n",
    "                return [L[-1][1],tail]\n",
    "            front += 1\n",
    "            tail += 1\n",
    "        return [-1,-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        dp = [[float('-inf'), float('inf')] for _ in range(n)]\n",
    "        maxidx = [-1]*n\n",
    "        minidx = [-1]*n\n",
    "        dp[n-1][0], dp[n-1][1] = nums[n-1], nums[n-1]\n",
    "        maxidx[n-1], minidx[n-1] = n-1, n-1\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if(nums[i] > dp[i+1][0]):\n",
    "                dp[i][0] = nums[i]\n",
    "                maxidx[i] = i \n",
    "            else:\n",
    "                dp[i][0] = dp[i+1][0]\n",
    "                maxidx[i] = maxidx[i+1]\n",
    "            if(nums[i] < dp[i+1][1]):\n",
    "                dp[i][1] = nums[i]\n",
    "                minidx[i] = i \n",
    "            else:\n",
    "                dp[i][1] = dp[i+1][1]\n",
    "                minidx[i] = minidx[i+1]\n",
    "        for i in range(n):\n",
    "            if(i+indexDifference < n):\n",
    "                if(abs(nums[i] - dp[i+indexDifference][0])>=valueDifference):\n",
    "                    return [i,maxidx[i+indexDifference]]\n",
    "                if(abs(nums[i] - dp[i+indexDifference][1])>=valueDifference):\n",
    "                    return [i,minidx[i+indexDifference]]\n",
    "            else:\n",
    "                break\n",
    "        return [-1,-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        if n <= indexDifference or max(nums) - min(nums) < valueDifference:\n",
    "            return [-1, -1]\n",
    "        s = sorted(((n, i) for i, n in enumerate(nums)), key = lambda x: -x[0])\n",
    "        #print(s)\n",
    "        \n",
    "        for i in range(n):\n",
    "            j = n - 1\n",
    "            while j >= i:\n",
    "                if s[i][0] - s[j][0] < valueDifference:\n",
    "                    break\n",
    "                if abs(s[i][1] - s[j][1]) >= indexDifference:\n",
    "                    return [s[i][1], s[j][1]]\n",
    "                j -= 1\n",
    "        \n",
    "        return [-1, -1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findIndices(self, nums, indexDifference: int, valueDifference: int) -> List[int]:\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] = (nums[i], i)\n",
    "        nums.sort(key=lambda x: x[0])\n",
    "        if abs(nums[-1][0] - nums[0][0]) < valueDifference:\n",
    "            return [-1, -1]\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(len(nums) - 1, i - 1, -1):\n",
    "                if abs(nums[i][0] - nums[j][0]) < valueDifference:\n",
    "                    break\n",
    "                if abs(nums[i][1] - nums[j][1]) >= indexDifference:\n",
    "                    return [nums[i][1], nums[j][1]]\n",
    "        return [-1, -1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIndices(self, nums: List[int], idx: int, vax: int) -> List[int]:\n",
    "        n=len(nums)\n",
    "        suf,id_=[],[]\n",
    "        suf.append((0,0))\n",
    "        id_.append((0,0))\n",
    "        suf.append((nums[-1],nums[-1]))\n",
    "        id_.append((n-1,n-1))\n",
    "        for i in range(n-2,-1,-1):\n",
    "            x,y=suf[-1]\n",
    "            ix,iy=id_[-1]\n",
    "            if nums[i]<x:\n",
    "                x=nums[i]\n",
    "                ix=i\n",
    "            if nums[i]>y:\n",
    "                y=nums[i]\n",
    "                iy=i\n",
    "\n",
    "            suf.append((x,y))\n",
    "            id_.append((ix,iy))\n",
    "        for i in range(n-idx):\n",
    "            x,y=suf[n-i-idx]\n",
    "            ix,iy=id_[n-i-idx]\n",
    "            if abs(x-nums[i])>=vax:\n",
    "                return [i,ix]\n",
    "            if abs(y-nums[i])>=vax:\n",
    "                return [i,iy]\n",
    "        return [-1,-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        dp = [[float('-inf'), float('inf')] for _ in range(n)]\n",
    "        maxidx = [-1]*n\n",
    "        minidx = [-1]*n\n",
    "        dp[n-1][0], dp[n-1][1] = nums[n-1], nums[n-1]\n",
    "        maxidx[n-1], minidx[n-1] = n-1, n-1\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if(nums[i] > dp[i+1][0]):\n",
    "                dp[i][0] = nums[i]\n",
    "                maxidx[i] = i \n",
    "            else:\n",
    "                dp[i][0] = dp[i+1][0]\n",
    "                maxidx[i] = maxidx[i+1]\n",
    "            if(nums[i] < dp[i+1][1]):\n",
    "                dp[i][1] = nums[i]\n",
    "                minidx[i] = i \n",
    "            else:\n",
    "                dp[i][1] = dp[i+1][1]\n",
    "                minidx[i] = minidx[i+1]\n",
    "        for i in range(n):\n",
    "            if(i+indexDifference < n):\n",
    "                if(abs(nums[i] - dp[i+indexDifference][0])>=valueDifference):\n",
    "                    return [i,maxidx[i+indexDifference]]\n",
    "                if(abs(nums[i] - dp[i+indexDifference][1])>=valueDifference):\n",
    "                    return [i,minidx[i+indexDifference]]\n",
    "            else:\n",
    "                break\n",
    "        return [-1,-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        r_max = [[0, 0] for _ in range(n)]\n",
    "        r_min = [[0, 0] for _ in range(n)]\n",
    "        tmp = 0\n",
    "        index = n - 1\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if tmp < nums[i]:\n",
    "                index = i\n",
    "                tmp = nums[i]\n",
    "            r_max[i][0] = tmp\n",
    "            r_max[i][1] = index\n",
    "        \n",
    "        tmp = inf\n",
    "        index = n - 1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if tmp > nums[i]:\n",
    "                index = i\n",
    "                tmp = nums[i]\n",
    "            r_min[i][0] = tmp\n",
    "            r_min[i][1] = index\n",
    "        \n",
    "        for i in range(n):\n",
    "            j = i + indexDifference\n",
    "            if j < n:\n",
    "                if abs(r_max[j][0] - nums[i]) >= valueDifference:\n",
    "                    return [i, r_max[j][1]]\n",
    "                if abs(r_min[j][0] - nums[i]) >= valueDifference:\n",
    "                    return [i, r_min[j][1]]\n",
    "        \n",
    "        return [-1, -1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [-1,-1]\n",
    "        maxv = [[0,0]]*(n+10)\n",
    "        minv = [[0,0]]*(n+10)\n",
    "        mx = -1<<31\n",
    "        idx1,idx2 = 0,0\n",
    "        mn = 1<<31\n",
    "        \n",
    "        for i in range(n-1,-1,-1):\n",
    "            if mx<nums[i]:\n",
    "                idx1 = i\n",
    "                mx = nums[i]\n",
    "            if mn>nums[i]:\n",
    "                idx2 = i\n",
    "                mn = nums[i]\n",
    "            maxv[i] = [mx,idx1]\n",
    "            minv[i] = [mn,idx2]\n",
    "        \n",
    "        for i in range(n):\n",
    "            r = i+indexDifference\n",
    "            if r>=n:break\n",
    "            if abs(maxv[r][0]-nums[i])>=valueDifference:\n",
    "                ans = [i,maxv[r][1]]\n",
    "                break\n",
    "            if abs(minv[r][0]-nums[i])>=valueDifference:\n",
    "                ans = [i,minv[r][1]]\n",
    "                break\n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import Queue\n",
    "from sortedcontainers import SortedList\n",
    "class Node:\n",
    "    def __init__(self, pos, val):\n",
    "        self.pos = pos\n",
    "        self.val = val\n",
    "    def __lt__(self, other):\n",
    "        return self.val < other.val\n",
    "    \n",
    "class Solution:\n",
    "    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:\n",
    "        sortlist = SortedList([])\n",
    "        inque = Queue()\n",
    "        listnum = 0\n",
    "        for idx, item in enumerate(nums):\n",
    "            inque.put(Node(idx, item))\n",
    "            if idx >= indexDifference:\n",
    "                now = inque.get()\n",
    "                sortlist.add(now)\n",
    "                listnum += 1\n",
    "            if listnum > 0:\n",
    "                startnode = sortlist[0]\n",
    "                endnode = sortlist[listnum-1]\n",
    "                if abs(startnode.val - item) >= valueDifference:\n",
    "                    return [startnode.pos, idx]\n",
    "                if abs(endnode.val - item) >= valueDifference:\n",
    "                    return [endnode.pos, idx]\n",
    "            \n",
    "        return [-1, -1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        mp = {}\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if nums[i] not in mp:\n",
    "                mp[nums[i]] = [i, i]\n",
    "            else:\n",
    "                if i < mp[nums[i]][0]:\n",
    "                    mp[nums[i]][0] = i\n",
    "                if i > mp[nums[i]][1]:\n",
    "                    mp[nums[i]][1] = i\n",
    "        bi = sorted(mp.keys())\n",
    "        m = len(bi)\n",
    "        for i in range(n):\n",
    "            j = nums[i] + valueDifference\n",
    "            idx = bisect_left(bi, j)\n",
    "            # print(\"1@\",j,idx,nums[i])\n",
    "            for ii in range(idx, m):\n",
    "                tidx = mp[bi[ii]]\n",
    "                if i - tidx[0] >= indexDifference:\n",
    "                    return [tidx[0], i]\n",
    "                if tidx[1]-i >= indexDifference:\n",
    "                    return [i, tidx[1]]\n",
    "            # j = nums[i] - valueDifference\n",
    "            # idx = bisect_right(bi, j)\n",
    "            # # print(j,idx)\n",
    "            # if idx:\n",
    "            #     print(\"2@\",j,idx,nums[i])\n",
    "            #     idx -= 1\n",
    "            #     tidx = mp[bi[idx]]\n",
    "            #     if abs(tidx - i) >= indexDifference:\n",
    "            #         return [i, tidx]\n",
    "            \n",
    "        return [-1, -1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIndices(self, nums: List[int], index: int, value: int) -> List[int]:\n",
    "        \n",
    "        ans = [-1,-1]\n",
    "        n = len(nums)\n",
    "        hashmap = [[] for _ in range(n)]\n",
    "        \n",
    "        for i , num in enumerate(nums):\n",
    "            if len(hashmap[i-1]) == 1:\n",
    "                hashmap[i] = [hashmap[i-1][0]]\n",
    "            elif len(hashmap[i-1]) > 1:\n",
    "                hashmap[i] = [hashmap[i-1][0],hashmap[i-1][-1]]\n",
    "            bisect.insort(hashmap[i],(num,i))\n",
    "            if i - index >= 0:\n",
    "                if abs(num - hashmap[i-index][0][0]) >= value:\n",
    "                    return [hashmap[i-index][0][1],i]\n",
    "                if abs(num - hashmap[i-index][-1][0]) >= value:\n",
    "                    return [hashmap[i-index][-1][1],i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:\n",
    "        dic = defaultdict(list)\n",
    "        for i,k in enumerate(nums):\n",
    "            dic[k].append(i)\n",
    "        l = sorted(list(dic.keys()))\n",
    "        n = len(l)\n",
    "        ans = [-1,-1]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if l[i] - valueDifference < 0:\n",
    "                continue\n",
    "            idx = bisect_right(l,l[i]-valueDifference)\n",
    "            for nn in l[:idx]:\n",
    "                if abs(dic[l[i]][-1]-dic[nn][0])>=indexDifference:\n",
    "                    return [dic[nn][0],dic[l[i]][-1]]\n",
    "                elif abs(dic[l[i]][0]-dic[nn][-1])>=indexDifference:\n",
    "                    return [dic[nn][-1],dic[l[i]][0]]\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        if n <= indexDifference:\n",
    "            return [-1,-1]\n",
    "        if indexDifference == 0:\n",
    "            arr = [[y,x] for x,y in enumerate(nums)]\n",
    "            arr.sort()\n",
    "            if arr[-1][0] - arr[0][0] >= valueDifference:\n",
    "                return [arr[0][1],arr[-1][1]]\n",
    "        if n < 2:\n",
    "            return [-1,-1]\n",
    "        def search(arr):\n",
    "            stack = SortedList()\n",
    "            k = 0\n",
    "            for i in range(indexDifference,n):\n",
    "                stack.add([arr[k],k])\n",
    "                k += 1\n",
    "                if stack[-1][0]-arr[i] >= valueDifference:\n",
    "                    return [i,stack[-1][1]]\n",
    "                elif arr[i] - stack[0][0] >= valueDifference:\n",
    "                    return [stack[0][1],i]\n",
    "            return [-1,-1]\n",
    "        if search(nums) != [-1,-1]:\n",
    "            return search(nums)\n",
    "        return search(nums[::-1])\n",
    "\n",
    "            \n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIndices(self, nums: List[int], indexDifference: int, valueDifference: int) -> List[int]:\n",
    "        minh = []\n",
    "        maxh = []\n",
    "        \n",
    "        n = len(nums)\n",
    "        \n",
    "        for i in range(indexDifference, n):\n",
    "            heapq.heappush(minh, (nums[i - indexDifference], i - indexDifference))\n",
    "            heapq.heappush(maxh, (-nums[i - indexDifference], i - indexDifference))\n",
    "            \n",
    "\n",
    "            if nums[i] - minh[0][0] >= valueDifference:\n",
    "                return [minh[0][1], i]\n",
    "            elif  valueDifference + nums[i] + maxh[0][0] <= 0:\n",
    "                return [maxh[0][1], i]\n",
    "        return [-1, -1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
